{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Range Covering Elements from K Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting #sliding-window #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序 #滑动窗口 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestRange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有&nbsp;<code>k</code>&nbsp;个 <strong>非递减排列</strong> 的整数列表。找到一个 <strong>最小 </strong>区间，使得&nbsp;<code>k</code>&nbsp;个列表中的每个列表至少有一个数包含在其中。</p>\n",
    "\n",
    "<p>我们定义如果&nbsp;<code>b-a &lt; d-c</code>&nbsp;或者在&nbsp;<code>b-a == d-c</code>&nbsp;时&nbsp;<code>a &lt; c</code>，则区间 <code>[a,b]</code> 比 <code>[c,d]</code> 小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]\n",
    "<strong>输出：</strong>[20,24]\n",
    "<strong>解释：</strong> \n",
    "列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。\n",
    "列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。\n",
    "列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[1,2,3],[1,2,3],[1,2,3]]\n",
    "<strong>输出：</strong>[1,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == k</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 3500</code></li>\n",
    "\t<li><code>1 &lt;= nums[i].length &lt;= 50</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 按非递减顺序排列</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-range-covering-elements-from-k-lists](https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-range-covering-elements-from-k-lists](https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]', '[[1,2,3],[1,2,3],[1,2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        h = []\n",
    "        k = len(nums)\n",
    "        lo = float('inf')\n",
    "        hi = float('-inf')\n",
    "        for i in range(k):\n",
    "            lo = min(lo, nums[i][0])\n",
    "            hi = max(hi, nums[i][0])\n",
    "            heapq.heappush(h, (nums[i].pop(0), i))\n",
    "        gap = hi - lo\n",
    "        ans = [lo, hi]\n",
    "        while True:\n",
    "            v, idx = heapq.heappop(h)\n",
    "            if not nums[idx]:\n",
    "                break\n",
    "            new_v = nums[idx].pop(0)\n",
    "            heapq.heappush(h, (new_v, idx))\n",
    "            lo = h[0][0]\n",
    "            hi = max(hi, new_v)\n",
    "            if gap > hi - lo:\n",
    "                gap = hi - lo\n",
    "                ans = [lo, hi]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        hashmap = collections.defaultdict(list)  #创建一个值是列表的字典\n",
    "        xMin,xMax = 10**5,-10**5  #初始化最小值和最大值\n",
    "\n",
    "        for i,vec in enumerate(nums):  #把每个数字出现过的列表添加到字典该数作为键，值的列表中\n",
    "            for x in vec:\n",
    "                hashmap[x].append(i)  #添加对应值\n",
    "            xMin = min(xMin,*vec)\n",
    "            xMax = max(xMax,*vec)  #找到数字所在范围 \n",
    "\n",
    "        freq = [0] * n  #在当前窗口的情况下对应列表编号的出现次数\n",
    "        inside = 0  #窗口中已有的列表数\n",
    "        left,right = xMin,xMin-1  #两个指针的初始位置\n",
    "        bestLeft,bestRight = xMin,xMax  #返回窗口的初始位置\n",
    "\n",
    "        while right < xMax:  #指针对应的是整数值，在范围内每次加1遍历\n",
    "            \"\"\"\n",
    "            指向窗口右边界的指针右移当且仅当每次遍历到新的元素，\n",
    "            并将这个新的元素对应的值数组中的每一个数加入到哈希表中\n",
    "            \"\"\"\n",
    "            right += 1\n",
    "            if right in hashmap:  #这个数出现在了之前的列表中\n",
    "                for x in hashmap[right]:  #遍历这个数出现过的每一个列表编号\n",
    "                    freq[x] += 1  #在当前窗口的情况下对应列表编号的出现次数+1\n",
    "                    if freq[x] == 1:  #如果对应列表初次出现了 \n",
    "                    #窗口中就出现了新列表 此时窗口中已有列表数+1\n",
    "                        inside += 1 \n",
    "            while inside == n:  #窗口中已经包含了全部的列表 \n",
    "                \"\"\"\n",
    "                答案更新当且仅当当前窗口内的元素包含 A 中所有的元素\n",
    "                \"\"\"\n",
    "                if right - left < bestRight - bestLeft:  #维护最小窗口\n",
    "                    bestLeft,bestRight = left,right \n",
    "                if left in hashmap:\n",
    "                    \"\"\"\n",
    "                    指向窗口右边界的指针右移当且仅当每次遍历到新的元素，\n",
    "                    并将这个新的元素对应的值数组中的每一个数加入到哈希表中\n",
    "                    \"\"\"\n",
    "                    for x in hashmap[left]:\n",
    "                        freq[x] -= 1 \n",
    "                        if freq[x] == 0:  #对应列表出现次数为0 也就是不见了\n",
    "                            inside -= 1  #窗口中对应列表数就-1\n",
    "                left += 1  #左指针向右移动 \n",
    "                #也就是题解里说的 \n",
    "                #指向窗口左边界的指针右移当且仅当当前窗口内的元素包含 A 中所有的元素，\n",
    "                #同时将原来左边界对应的值数组的元素们从哈希表中移除\n",
    "\n",
    "        return [bestLeft,bestRight]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        nums_dict = defaultdict(list)\n",
    "        max_val = nums[0][0]\n",
    "        min_val = nums[0][0]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                # 构造字典[num: 行号]\n",
    "                nums_dict[nums[i][j]].append(i)\n",
    "                max_val = max(nums[i][j], max_val)\n",
    "                min_val = min(nums[i][j], min_val)\n",
    "\n",
    "        visit = [0] * len(nums) # 某行是否满足条件\n",
    "        cnt = 0\n",
    "        left = min_val\n",
    "        start = -sys.maxsize - 1\n",
    "        end = sys.maxsize\n",
    "        for right in range(min_val, max_val + 1):\n",
    "            if right in nums_dict.keys():\n",
    "                index_list = nums_dict[right]\n",
    "                for i in index_list:\n",
    "                    visit[i] += 1\n",
    "                    # 首次遍历，更新cnt\n",
    "                    if visit[i] == 1:\n",
    "                        cnt += 1\n",
    "                # 所有行都满足条件,[left， right]\n",
    "                while cnt == len(nums):\n",
    "                    if left in nums_dict.keys():\n",
    "                        if right - left < end - start:\n",
    "                            start, end = left, right\n",
    "                        left_list = nums_dict[left]\n",
    "                        for i in left_list:\n",
    "                            visit[i] -= 1\n",
    "                            if visit[i] == 0:\n",
    "                                cnt -= 1\n",
    "                    left += 1 # 继续查找最小区间\n",
    "\n",
    "        return [start, end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        nums_dict = defaultdict(list)\n",
    "        max_val = nums[0][0]\n",
    "        min_val = nums[0][0]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                # 构造字典[num: 行号]\n",
    "                nums_dict[nums[i][j]].append(i)\n",
    "                max_val = max(nums[i][j], max_val)\n",
    "                min_val = min(nums[i][j], min_val)\n",
    "\n",
    "        visit = [0] * len(nums) # 某行是否满足条件\n",
    "        cnt = 0\n",
    "        left = min_val\n",
    "        start = -sys.maxsize - 1\n",
    "        end = sys.maxsize\n",
    "        for right in range(min_val, max_val + 1):\n",
    "            if right in nums_dict.keys():\n",
    "                index_list = nums_dict[right]\n",
    "                for i in index_list:\n",
    "                    visit[i] += 1\n",
    "                    # 首次遍历，更新cnt\n",
    "                    if visit[i] == 1:\n",
    "                        cnt += 1\n",
    "                # 所有行都满足条件\n",
    "                while cnt == len(nums):\n",
    "                    if left in nums_dict.keys():\n",
    "                        if right - left < end - start:\n",
    "                            start, end = left, right\n",
    "                        left_list = nums_dict[left]\n",
    "                        for i in left_list:\n",
    "                            visit[i] -= 1\n",
    "                            if visit[i] == 0:\n",
    "                                cnt -= 1\n",
    "                    left += 1\n",
    "\n",
    "        return [start, end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        helper = [1] * n\n",
    "        rest = n\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for num in nums[i]:\n",
    "                dic[num].append(i)\n",
    "        \n",
    "        a = sorted(dic.keys())\n",
    "        left = -inf\n",
    "        right = inf\n",
    "        cur = 0\n",
    "        for i in range(len(a)):\n",
    "            for j in dic[a[i]]:\n",
    "                helper[j] -= 1\n",
    "                if helper[j] == 0: rest -= 1\n",
    "            while rest == 0 and cur <= i:\n",
    "                if right - left > a[i] - a[cur]:\n",
    "                    left = a[cur]\n",
    "                    right = a[i]\n",
    "                for j in dic[a[cur]]:\n",
    "                    helper[j] += 1\n",
    "                    if helper[j] > 0: rest += 1\n",
    "                cur += 1\n",
    "        return [left, right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class E:\n",
    "    def __init__(self, value, index):\n",
    "        self.value = value\n",
    "        self.index = index\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.value < other.value\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "        sl = []\n",
    "        ans = (1e10, 0, 0)\n",
    "        for i in range(len(nums)):\n",
    "            bisect.insort(sl, E(nums[i][0], i))\n",
    "        while True:\n",
    "            assert len(sl) == len(nums)\n",
    "            maxDiff = sl[-1].value - sl[0].value\n",
    "            if maxDiff < ans[0]:\n",
    "                ans = (maxDiff, sl[0].value, sl[-1].value)\n",
    "            e = sl.pop(0)\n",
    "            index = e.index\n",
    "            if nums[e.index]:\n",
    "                new_e = E(nums[e.index].pop(0), e.index)\n",
    "            else:\n",
    "                break\n",
    "            bisect.insort(sl, new_e)\n",
    "        return [ans[1], ans[2]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        range_list = []\n",
    "        k_list = []\n",
    "        range_val = [-float(\"inf\"), float(\"inf\")]\n",
    "        k = len(nums)\n",
    "        for i in range(k):\n",
    "            new = nums[i][0]\n",
    "            heapq.heappush(range_list, (new, i, 0))\n",
    "            heapq.heappush(k_list, new)\n",
    "        print(k_list)\n",
    "\n",
    "        while len(range_list) == k:\n",
    "            \n",
    "            if max(k_list) - min(k_list) < range_val[1]-range_val[0]:\n",
    "                print(k_list)\n",
    "                range_val = [min(k_list), max(k_list)]\n",
    "                \n",
    "            top, li, ei = heapq.heappop(range_list)\n",
    "            heapq.heappop(k_list)\n",
    "\n",
    "\n",
    "            if ei+1 < len(nums[li]):\n",
    "                heapq.heappush(range_list, (nums[li][ei+1], li, ei+1))\n",
    "                heapq.heappush(k_list, nums[li][ei+1])\n",
    "\n",
    "        return range_val\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        range_list = []\n",
    "        k_list = []\n",
    "        range_val = [-float(\"inf\"), float(\"inf\")]\n",
    "        k = len(nums)\n",
    "        for i in range(k):\n",
    "            new = nums[i][0]\n",
    "            heapq.heappush(range_list, (new, i, 0))\n",
    "            heapq.heappush(k_list, new)\n",
    "\n",
    "        while len(range_list) == k:\n",
    "\n",
    "            if max(k_list) - min(k_list) < range_val[1]-range_val[0]:\n",
    "                print(k_list)\n",
    "                range_val = [min(k_list), max(k_list)]\n",
    "\n",
    "            top, li, ei = heapq.heappop(range_list)\n",
    "            heapq.heappop(k_list)\n",
    "            \n",
    "            if ei+1 < len(nums[li]):\n",
    "                heapq.heappush(range_list, (nums[li][ei+1], li, ei+1))\n",
    "                heapq.heappush(k_list, nums[li][ei+1])\n",
    "\n",
    "        return range_val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        sd = SortedList()\n",
    "        for i, l in enumerate(nums):\n",
    "            sd.add((l[0], i, 0))\n",
    "        d = inf\n",
    "        ans = None\n",
    "        while True:\n",
    "            cur = sd[-1][0] - sd[0][0]\n",
    "            if cur < d:\n",
    "                d = cur\n",
    "                ans = [sd[0][0], sd[-1][0]]\n",
    "            elif cur == d and sd[0][0] < ans[0]:\n",
    "                ans = [sd[0][0], sd[-1][0]]\n",
    "            \n",
    "            _, i, j = sd.pop(0)\n",
    "            if j + 1 == len(nums[i]):\n",
    "                break\n",
    "            sd.add((nums[i][j+1], i, j + 1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j],i))\n",
    "        \n",
    "        lst.sort(key=lambda x:x[0])\n",
    "        #print(lst)\n",
    "        i = 0\n",
    "        k = 0\n",
    "        ans = [-10**9, 10**9]\n",
    "        count = {}\n",
    "        for j in range(len(lst)):\n",
    "            if lst[j][1] not in count.keys():\n",
    "                k+=1\n",
    "                count[lst[j][1]] = 1\n",
    "            else:\n",
    "                count[lst[j][1]] += 1\n",
    "            if k>=len(nums):\n",
    "                while count[lst[i][1]]>1:\n",
    "                    count[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "                if ans[1]-ans[0]>lst[j][0]-lst[i][0]:\n",
    "                    ans[1],ans[0] = lst[j][0],lst[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        owner_arr, merged_arr = self.merge_arrays(nums)\n",
    "        n = len(owner_arr)\n",
    "        k = len(nums)\n",
    "\n",
    "        min_zone = [merged_arr[0], merged_arr[-1]]\n",
    "        my_dict = {}\n",
    "        for i in range(n):\n",
    "            if len(my_dict) < k and owner_arr[i] in my_dict:\n",
    "                del my_dict[owner_arr[i]]\n",
    "\n",
    "            my_dict[owner_arr[i]] = merged_arr[i]\n",
    "\n",
    "            if len(my_dict) == k:\n",
    "                my_items = list(my_dict.items())\n",
    "                begin_item, end_item = my_items[0], my_items[-1]\n",
    "\n",
    "                if end_item[1] - begin_item[1] < min_zone[1] - min_zone[0]:\n",
    "                    min_zone = [begin_item[1], end_item[1]]\n",
    "                del my_dict[begin_item[0]]\n",
    "\n",
    "        return min_zone\n",
    "\n",
    "    def merge_arrays(self, nums: List[List[int]]):\n",
    "        owner_arr = []\n",
    "        merged_arr = []\n",
    "        heap = []\n",
    "        for arr_id, arr in enumerate(nums):\n",
    "            if len(arr) == 0:\n",
    "                continue\n",
    "\n",
    "            heapq.heappush(heap, (arr[0], arr_id, 0))\n",
    "\n",
    "        while len(heap):\n",
    "            val, arr_id, arr_index = heapq.heappop(heap)\n",
    "            owner_arr.append(arr_id)\n",
    "            merged_arr.append(val)\n",
    "\n",
    "            if arr_index + 1 < len(nums[arr_id]):\n",
    "                heapq.heappush(heap, (nums[arr_id][arr_index + 1], arr_id, arr_index + 1))\n",
    "\n",
    "        return owner_arr, merged_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        all_nums = []\n",
    "\n",
    "        pq = []\n",
    "        for i, subnums in enumerate(nums):\n",
    "            heapq.heappush(pq, (subnums[0], i, 0))\n",
    "        \n",
    "        while pq:\n",
    "            val, row_idx, col_idx = heapq.heappop(pq)\n",
    "            all_nums.append((val, row_idx))\n",
    "\n",
    "            if col_idx + 1 < len(nums[row_idx]):\n",
    "                heapq.heappush(pq, (nums[row_idx][col_idx+1], row_idx, col_idx+1))\n",
    "        \n",
    "        n = len(all_nums)\n",
    "\n",
    "        valid = 0\n",
    "        window = defaultdict(int)\n",
    "\n",
    "        left = right = 0\n",
    "        ans_start, ans_dist = 0, 10**9\n",
    "        # print(all_nums)\n",
    "        while right < n:\n",
    "            val, row_idx = all_nums[right]\n",
    "            right += 1\n",
    "            window[row_idx] += 1\n",
    "\n",
    "            if window[row_idx] == 1:\n",
    "                valid += 1\n",
    "\n",
    "            # print(left, right, valid, window)\n",
    "            while valid == len(nums):\n",
    "                left_val, left_row_idx = all_nums[left]\n",
    "                cur_dist = val - left_val\n",
    "                if cur_dist < ans_dist:\n",
    "                    ans_start = left_val\n",
    "                    ans_dist = cur_dist\n",
    "                \n",
    "                left += 1\n",
    "\n",
    "                if window[left_row_idx] == 1:\n",
    "                    valid -= 1\n",
    "                window[left_row_idx] -= 1\n",
    "\n",
    "        return [ans_start, ans_start+ans_dist]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for k, v in enumerate(nums):\n",
    "            m1[k] = v\n",
    "        sd1 = SortedList(key=lambda x: x[1])\n",
    "        for i in m1:\n",
    "            first = m1[i].pop(0)\n",
    "            sd1.add((i, first))\n",
    "        ans = math.inf\n",
    "        ret = []\n",
    "        while True:\n",
    "            ans1 = sd1[-1][1] - sd1[0][1]\n",
    "            if ans1 < ans:\n",
    "                ans = ans1\n",
    "                ret = [sd1[0][1], sd1[-1][1]]\n",
    "            idx, val = sd1.pop(0)\n",
    "            if len(m1[idx]) == 0:\n",
    "                break\n",
    "            newv = m1[idx].pop(0)\n",
    "            sd1.add((idx, newv))\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        # 滑窗法，总的时间复杂度为O(nk(log(nk)))，空间复杂度为O(nk)\n",
    "\n",
    "        # step1: 把所有元素和它的行数保存在li中，从小到大排序\n",
    "        # 时间复杂度O(nk(log(nk)))\n",
    "        li = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                li.append([nums[i][j], i])\n",
    "        li.sort()\n",
    "\n",
    "        # step2: 滑窗，li中每个元素最多访问两次，时间复杂度O(nk)\n",
    "        visited = [0] * len(nums)\n",
    "        count = 0\n",
    "        left = 0\n",
    "        start, end = -10**5, 10**5\n",
    "        for right in range(len(li)):\n",
    "            visited[li[right][1]] += 1\n",
    "            if visited[li[right][1]] == 1:\n",
    "                count += 1\n",
    "                while count == len(nums):\n",
    "                    if li[right][0] - li[left][0] < end - start:\n",
    "                        start, end = li[left][0], li[right][0]\n",
    "                    visited[li[left][1]] -= 1\n",
    "                    if visited[li[left][1]] == 0:\n",
    "                        count -= 1\n",
    "                    left += 1\n",
    "        return [start, end]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        if k == 1:\n",
    "            return [nums[0][0], nums[0][0]]\n",
    "        indexs = [0] * k\n",
    "        lists = []\n",
    "        largest = -10**5\n",
    "        import heapq\n",
    "        for i in range(k):\n",
    "            num = nums[i][0]\n",
    "            heapq.heappush(lists, (num, i))\n",
    "            largest = max(largest, num)\n",
    "        left, right = lists[0][0], largest\n",
    "        while True:\n",
    "            num, i = heapq.heappop(lists)\n",
    "            indexs[i] += 1\n",
    "            if indexs[i] >= len(nums[i]):\n",
    "                break\n",
    "            newnum = nums[i][indexs[i]]\n",
    "            heapq.heappush(lists, (newnum, i))\n",
    "            largest = max(largest, newnum)\n",
    "            if largest - lists[0][0] < right - left:\n",
    "                left, right = lists[0][0], largest\n",
    "        return [left, right]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [inf]*n\n",
    "        s = set()\n",
    "        x = -inf\n",
    "        y = inf\n",
    "        heap = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in nums[i]:\n",
    "                heap.append([j,i])\n",
    "        heapq.heapify(heap)\n",
    "        #print(heap)\n",
    "        while len(heap) > 0:\n",
    "            num,index = heapq.heappop(heap)\n",
    "            ans[index] = num\n",
    "            s.add(index)\n",
    "            if len(s) == n:\n",
    "                p,q = min(ans),max(ans)\n",
    "                if q-p < y-x:\n",
    "                    x = p\n",
    "                    y = q\n",
    "        return [x,y]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        if k == 1:\n",
    "            return [nums[0][0], nums[0][0]]\n",
    "        indexs = [0] * k\n",
    "        lists = []\n",
    "        largest = -10**5\n",
    "        import heapq\n",
    "        for i in range(k):\n",
    "            num = nums[i][0]\n",
    "            heapq.heappush(lists, (num, i))\n",
    "            largest = max(largest, num)\n",
    "        left, right = lists[0][0], largest\n",
    "        while True:\n",
    "            num, i = heapq.heappop(lists)\n",
    "            indexs[i] += 1\n",
    "            if indexs[i] >= len(nums[i]):\n",
    "                break\n",
    "            newnum = nums[i][indexs[i]]\n",
    "            heapq.heappush(lists, (newnum, i))\n",
    "            largest = max(largest, newnum)\n",
    "            if largest - lists[0][0] < right - left:\n",
    "                left, right = lists[0][0], largest\n",
    "        return [left, right]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        index_list=[0]*len(nums)\n",
    "        num_list=[item[0] for item in nums]\n",
    "        max_num=max(num_list)\n",
    "        min_num=min(num_list)\n",
    "        min_index=num_list.index(min_num)\n",
    "        result=[min_num,max_num]\n",
    "        min_window=result[1]-result[0]\n",
    "        while True:\n",
    "            if index_list[min_index]==len(nums[min_index])-1:\n",
    "                break\n",
    "            index_list[min_index]+=1\n",
    "            new_num=nums[min_index][index_list[min_index]]\n",
    "            num_list[min_index]=new_num\n",
    "            if new_num>max_num:\n",
    "                max_num=new_num\n",
    "            min_num=min(num_list)\n",
    "            min_index=num_list.index(min_num)\n",
    "            if max_num-min_num<min_window:\n",
    "                min_window=max_num-min_num\n",
    "                result[0]=min_num\n",
    "                result[1]=max_num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        index_list=[0]*len(nums)\n",
    "        num_list=[item[0] for item in nums]\n",
    "        max_num=max(num_list)\n",
    "        min_num=min(num_list)\n",
    "        min_index=num_list.index(min_num)\n",
    "        result=[min_num,max_num]\n",
    "        min_window=result[1]-result[0]\n",
    "        while True:\n",
    "            if index_list[min_index]==len(nums[min_index])-1:\n",
    "                break\n",
    "            index_list[min_index]+=1\n",
    "            new_num=nums[min_index][index_list[min_index]]\n",
    "            num_list[min_index]=new_num\n",
    "            if new_num>max_num:\n",
    "                max_num=new_num\n",
    "            min_num=min(num_list)\n",
    "            min_index=num_list.index(min_num)\n",
    "            if max_num-min_num<min_window:\n",
    "                min_window=max_num-min_num\n",
    "                result[0]=min_num\n",
    "                result[1]=max_num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        #枚举区间的右端点\n",
    "        #按顺序合并所有数组\n",
    "        #找到一个最小区间\n",
    "        bignums=[]\n",
    "        k1=len(nums)\n",
    "        for i,ns in enumerate(nums):\n",
    "            for num in ns:\n",
    "                bignums.append([num,i])\n",
    "        bignums.sort()\n",
    "        n=len(bignums)\n",
    "        i,k=0,0\n",
    "        count=defaultdict(int)\n",
    "        ans=[]\n",
    "        for r in range(n):\n",
    "            if count[bignums[r][1]]==0:\n",
    "                k+=1\n",
    "            count[bignums[r][1]]+=1\n",
    "            if k==k1:\n",
    "                while count[bignums[i][1]]>1:\n",
    "                    count[bignums[i][1]]-=1\n",
    "                    i+=1\n",
    "                if not ans or ans[1]-ans[0]>bignums[r][0]-bignums[i][0]:\n",
    "                    ans=[bignums[i][0],bignums[r][0]]\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: list[list[int]]) -> list[int]:\n",
    "        def find(list1,target):\n",
    "            left = 0\n",
    "            right =len(list1)-1\n",
    "            while left<right:\n",
    "                mid = (left+right)//2\n",
    "                if list1[mid]>=target:\n",
    "                    right=mid\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            return list1[left]\n",
    "        set1= set()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                set1.add(nums[i][j])\n",
    "        hashmap = sorted(list(set1))\n",
    "        max1=-10**5\n",
    "        min1 = 10**5\n",
    "        for i in range(len(nums)):\n",
    "            max1 = max(max1,max(nums[i]))\n",
    "            min1 = min(min1,min(nums[i]))\n",
    "        ans = [min1,max1]\n",
    "        for left in hashmap:\n",
    "            right = left\n",
    "            for j in range(len(nums)):\n",
    "                if nums[j][-1]<left:\n",
    "                    return ans\n",
    "                right = max(right,find(nums[j],left))\n",
    "            if right-left<ans[1]-ans[0]:\n",
    "                ans = [left,right]\n",
    "            if right-left==ans[1]-ans[0] and left<ans[0]:\n",
    "                ans = [left,right]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        if k == 1:\n",
    "            return [nums[0][0], nums[0][0]]\n",
    "        indexs = [0] * k\n",
    "        lists = []\n",
    "        largest = -10**5\n",
    "        import heapq\n",
    "        for i in range(k):\n",
    "            num = nums[i][0]\n",
    "            heapq.heappush(lists, (num, i))\n",
    "            largest = max(largest, num)\n",
    "        left, right = lists[0][0], largest\n",
    "        while True:\n",
    "            num, i = heapq.heappop(lists)\n",
    "            indexs[i] += 1\n",
    "            if indexs[i] >= len(nums[i]):\n",
    "                break\n",
    "            newnum = nums[i][indexs[i]]\n",
    "            heapq.heappush(lists, (newnum, i))\n",
    "            largest = max(largest, newnum)\n",
    "            if largest - lists[0][0] < right - left:\n",
    "                left, right = lists[0][0], largest\n",
    "        return [left, right]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        indexs = [0] * n\n",
    "        values = [0] * n\n",
    "        minv, maxv = 0, 0\n",
    "        for i in range(n):\n",
    "            values[i] = nums[i][0]\n",
    "\n",
    "        minv = -(10 ** 5)\n",
    "        maxv = 10 ** 5\n",
    "        # minv = min(values)\n",
    "        # maxv = max(values)\n",
    "\n",
    "        while True:\n",
    "            curmin, curmax = min(values), max(values)\n",
    "            if curmax - curmin < maxv - minv:\n",
    "                minv, maxv = curmin, curmax\n",
    "\n",
    "            i = values.index(curmin)\n",
    "            if indexs[i] < len(nums[i]) - 1:\n",
    "                indexs[i] += 1\n",
    "                values[i] = nums[i][indexs[i]]\n",
    "            else:\n",
    "                break\n",
    "        return [minv, maxv]\n",
    "\n",
    "\n",
    "# 起始时，窗口左侧指向0号位置，窗口右侧一直向右滑动，直到窗口内包含k组数。\n",
    "# 此时窗口左侧开始收缩，直到窗口左侧元素是该组唯一的元素。\n",
    "# 此时窗口左侧到窗口右侧就是最小区间。\n",
    "# 此后窗口右侧继续向右滑动，每滑动一次，就判断窗口左侧是否需要收缩，即判断窗口左侧元素是否是该组唯一的元素，如果是，收缩窗口左侧，直到窗口左侧元素是该组唯一的元素。\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "#         lst = []\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             for j in range(len(nums[i])):\n",
    "#                 lst.append((nums[i][j], i))\n",
    "#         res = [-(10 ** 5), 10 ** 5]\n",
    "#         lst.sort(key=lambda x: x[0])\n",
    "#         i, k = 0, 0\n",
    "#         count = collections.Counter()\n",
    "#         for j in range(len(lst)):\n",
    "#             if count[lst[j][1]] == 0:\n",
    "#                 k += 1\n",
    "#             count[lst[j][1]] += 1\n",
    "#             if k == n:\n",
    "#                 while count[lst[i][1]] > 1:\n",
    "#                     count[lst[i][1]] -= 1\n",
    "#                     i += 1\n",
    "#                 if res[1] - res[0] > lst[j][0] - lst[i][0]:\n",
    "#                     res[1], res[0] = lst[j][0], lst[i][0]\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        elem_id_index = [(elem[0], id, 0) for id, elem in enumerate(nums)]\n",
    "        heapq.heapify(elem_id_index)\n",
    "        minval = 1e-5\n",
    "        maxval = 1e5\n",
    "        curmax = max(elem_id_index)[0]\n",
    "\n",
    "        while elem_id_index:\n",
    "            curmin , id , index = heapq.heappop(elem_id_index)\n",
    "            if curmax-curmin<maxval-minval:\n",
    "                maxval = curmax\n",
    "                minval = curmin\n",
    "            if index < len(nums[id])-1:\n",
    "                val = nums[id][index+1]\n",
    "                curmax = max(curmax,val)\n",
    "                heapq.heappush(elem_id_index,(val,id,index+1))\n",
    "            else:\n",
    "                break\n",
    "        return [minval,maxval]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\r\n",
    "        Min,Max=float('inf'),float('-inf')\r\n",
    "        idx_map={}\r\n",
    "        L=len(nums)\r\n",
    "        for i,vec in enumerate(nums):\r\n",
    "            for x in vec:\r\n",
    "                Min=min(Min,x)\r\n",
    "                Max=max(Max,x)\r\n",
    "                rows=idx_map.setdefault(x,[])\r\n",
    "                rows.append(i)\r\n",
    "        best_left,best_right=Min,Max\r\n",
    "        left,right=Min,Min\r\n",
    "        freq=[0]*L\r\n",
    "        fit=0\r\n",
    "        while right<=Max:\r\n",
    "            if right in idx_map:\r\n",
    "                for rid in idx_map[right]:\r\n",
    "                    freq[rid]+=1\r\n",
    "                    if freq[rid]==1:\r\n",
    "                        fit+=1\r\n",
    "            while fit==L:\r\n",
    "                if right-left<best_right-best_left:\r\n",
    "                    best_left=left\r\n",
    "                    best_right=right\r\n",
    "                if left in idx_map:\r\n",
    "                    for rid in idx_map[left]:\r\n",
    "                        freq[rid]-=1\r\n",
    "                        if freq[rid]==0:\r\n",
    "                            fit-=1\r\n",
    "                left+=1\r\n",
    "            right+=1\r\n",
    "        return [best_left,best_right]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        minHeap = []\n",
    "        rangeStart, rangeEnd = 0, math.inf\n",
    "        currentMaxNum = -math.inf\n",
    "\n",
    "        for num in nums:\n",
    "            heappush(minHeap, (num[0], 0, num))\n",
    "            currentMaxNum = max(currentMaxNum, num[0])\n",
    "        \n",
    "        while len(minHeap) == len(nums):\n",
    "            num, i, list = heappop(minHeap)\n",
    "            if rangeEnd - rangeStart > currentMaxNum - num:\n",
    "                rangeStart = num\n",
    "                rangeEnd = currentMaxNum\n",
    "            if len(list) > i + 1:\n",
    "                heappush(minHeap, (list[i + 1], i + 1, list))\n",
    "                currentMaxNum = max(currentMaxNum, list[i + 1])\n",
    "        return[rangeStart, rangeEnd]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        # 找到最小区间至少每个都包含一个元素\n",
    "        k = len(nums)\n",
    "        index_list = [0] * k\n",
    "        elem_list = [0] * k\n",
    "        # 初始化，elem_list先取idx为0的元素\n",
    "        for i in range(k):\n",
    "            elem_list[i] = nums[i][index_list[i]]\n",
    "        minval, maxval = min(elem_list), max(elem_list)\n",
    "\n",
    "        # 遍历元素看是否存在更小区间\n",
    "        while True:\n",
    "            curmin, curmax = min(elem_list), max(elem_list)\n",
    "            if curmax - curmin < maxval - minval:\n",
    "                minval, maxval = curmin, curmax\n",
    "            # 当前最小id\n",
    "            idx = elem_list.index(curmin)\n",
    "            if index_list[idx] < len(nums[idx]) - 1:\n",
    "                index_list[idx] += 1\n",
    "                elem_list[idx] = nums[idx][index_list[idx]]\n",
    "            else:\n",
    "                break\n",
    "        return [minval, maxval]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\r\n",
    "        Min,Max=float('-inf'),float('inf')\r\n",
    "        max_val=max([vec[0] for vec in nums])\r\n",
    "        stack=[(vec[0],row,0) for row,vec in enumerate(nums)]\r\n",
    "        heapq.heapify(stack)\r\n",
    "        while True:\r\n",
    "            min_val,row,idx=heapq.heappop(stack)\r\n",
    "            if max_val-min_val<Max-Min:\r\n",
    "                Min=min_val\r\n",
    "                Max=max_val\r\n",
    "            idx+=1\r\n",
    "            if idx==len(nums[row]):\r\n",
    "                break\r\n",
    "            max_val=max(max_val,nums[row][idx])\r\n",
    "            heapq.heappush(stack,(nums[row][idx],row,idx))\r\n",
    "        return [Min,Max]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        # define variables\n",
    "        k = len(nums)\n",
    "        elem_id_index = [(elem[0], id, 0) for id, elem in enumerate(nums)]\n",
    "        heapq.heapify(elem_id_index)\n",
    "        maxval, minval = 1e5, -1e5\n",
    "        currmaxval = max(elem_id_index)[0]\n",
    "\n",
    "        # recursion\n",
    "        while True:\n",
    "            currminval, id, index = heapq.heappop(elem_id_index)\n",
    "            if currmaxval - currminval < maxval - minval:\n",
    "                maxval = currmaxval\n",
    "                minval = currminval\n",
    "            if index < len(nums[id]) - 1:\n",
    "                val = nums[id][index+1]\n",
    "                currmaxval = max(currmaxval, val)\n",
    "                heapq.heappush(elem_id_index, (val, id, index+1))\n",
    "            else:\n",
    "                break\n",
    "        return [minval, maxval]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        l, r = -10 ** 9, 10 ** 9\n",
    "        up = max(row[0] for row in nums)\n",
    "        h = [(num[0], i, 0) for i, num in enumerate(nums)]\n",
    "        heapify(h)\n",
    "        while True:\n",
    "            low, row, idx = heappop(h)\n",
    "            if up - low < r - l:\n",
    "                l, r = low, up\n",
    "            if idx == len(nums[row]) - 1:\n",
    "                break\n",
    "            num = nums[row][idx + 1]\n",
    "            up = max(up, num)\n",
    "            heappush(h, (num, row, idx + 1))\n",
    "        return [l, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums):\n",
    "        n = len(nums)\n",
    "        temp_dict = {}\n",
    "        value_min = - 10 ** 5\n",
    "        value_max = 10 ** 5\n",
    "        for i, item in enumerate(nums):\n",
    "            for j in item:\n",
    "                if j in temp_dict:\n",
    "                    temp_dict[j].append(i)\n",
    "                else:\n",
    "                    temp_dict[j] = [i]\n",
    "            value_min = min(value_min, *item)\n",
    "            value_max = max(value_max, *item)\n",
    "        \n",
    "        left, right = value_min, value_min - 1\n",
    "        best_left, best_right = value_min, value_max\n",
    "        inside_num = 0\n",
    "        freq = [0] * n\n",
    "        while right < value_max:\n",
    "            right += 1\n",
    "            if right in temp_dict:\n",
    "                for item in temp_dict[right]:\n",
    "                    freq[item] += 1\n",
    "                    if freq[item] == 1:\n",
    "                        inside_num += 1\n",
    "                while inside_num == n:\n",
    "                    if right - left < best_right - best_left:\n",
    "                        best_left, best_right = left, right\n",
    "                    if left in temp_dict:\n",
    "                        for k in temp_dict[left]:\n",
    "                            freq[k] -= 1\n",
    "                            if freq[k] == 0:\n",
    "                                inside_num -= 1\n",
    "                    left += 1\n",
    "        return [best_left, best_right]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        l, r = -10 ** 6, 10 ** 6\n",
    "        mx = max(row[0] for row in nums)\n",
    "        h = [(row[0], i, 0) for i, row in enumerate(nums)]\n",
    "        heapify(h)\n",
    "        while True:\n",
    "            mn, i, j = heappop(h)\n",
    "            if mx - mn < r - l:\n",
    "                l, r = mn, mx\n",
    "            if j == len(nums[i]) - 1:\n",
    "                break\n",
    "            j += 1\n",
    "            mx = max(mx, nums[i][j])\n",
    "            heappush(h, (nums[i][j], i, j))\n",
    "        return (l, r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        if k == 1:\n",
    "            return [nums[0][0], nums[0][0]]\n",
    "        indexs = [0] * k\n",
    "        lists = []\n",
    "        largest = -10 ** 5\n",
    "        import heapq\n",
    "        # 生成大小为k的堆\n",
    "        for i in range(k):\n",
    "            num = nums[i][0]\n",
    "            heapq.heappush(lists, (num, i))\n",
    "            largest = max(largest, num)\n",
    "\n",
    "        left, right = lists[0][0], largest\n",
    "\n",
    "        while True:\n",
    "            num, i = heapq.heappop(lists)\n",
    "            # 取出最小的数，以及对应的列表的下标\n",
    "            indexs[i] += 1\n",
    "            # 下标+1\n",
    "            if indexs[i] >= len(nums[i]):  # 退出循环\n",
    "                break\n",
    "            # 通过下标i找到列表，再通过indexs数组找到下一个元素的下标\n",
    "            newnum = nums[i][indexs[i]]\n",
    "            heapq.heappush(lists, (newnum, i))  # 插入新的数\n",
    "            largest = max(largest, newnum)  # 更新最大值\n",
    "            if largest - lists[0][0] < right - left:  # 更新区间\n",
    "                left, right = lists[0][0], largest\n",
    "        return [left, right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        heap = [(nums[i][0], i, 0) for i in range(n)]\n",
    "        heapify(heap)\n",
    "        mx = max(heap, key = lambda x: x[0])[0]\n",
    "        ans = [heap[0][0], mx]\n",
    "        while heap:\n",
    "            x, i, j = heappop(heap)\n",
    "            if j + 1 < len(nums[i]):\n",
    "                heappush(heap, (nums[i][j + 1], i, j + 1))\n",
    "                mx = max(mx, nums[i][j + 1])\n",
    "                mn = heap[0][0]\n",
    "                if mx - mn < ans[1] - ans[0] or (mx - mn == ans[1] - ans[0] and mn < ans[0]):\n",
    "                    ans = [mn, mx]\n",
    "\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        heap = [(nums[i][0],i,0)for i in range(len(nums))]\n",
    "        range_left, range_right = -10**9, 10**9\n",
    "        maxValue = max(vec[0] for vec in nums)\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        while True:\n",
    "            minValue, row, idx = heapq.heappop(heap)\n",
    "            if maxValue-minValue < range_right - range_left:\n",
    "                range_left, range_right = minValue, maxValue\n",
    "            if idx == len(nums[row]) - 1:\n",
    "                break\n",
    "            maxValue = max(maxValue, nums[row][idx+1])\n",
    "            heapq.heappush(heap, (nums[row][idx+1], row, idx+1))\n",
    "        return [range_left, range_right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        need = defaultdict(list)\n",
    "        imin, imax = sys.maxsize, -sys.maxsize\n",
    "        for i, vec in enumerate(nums):\n",
    "            imin = min(*vec, imin)\n",
    "            imax = max(*vec, imax)\n",
    "            for x in vec:\n",
    "                need[x].append(i)\n",
    "        \n",
    "        valid = 0\n",
    "        l, r = imin, imin\n",
    "        lbest, rbest = imin, imax\n",
    "        window = defaultdict(int)\n",
    "        while r <= imax:\n",
    "            if r in need:\n",
    "                for x in need[r]:\n",
    "                    window[x] += 1\n",
    "                    if window[x] == 1:\n",
    "                        valid += 1\n",
    "\n",
    "            while valid == n:\n",
    "                if r - l < rbest - lbest:\n",
    "                    lbest, rbest = l, r\n",
    "                if l in need:\n",
    "                    for x in need[l]:\n",
    "                        if window[x] == 1:\n",
    "                            valid -= 1\n",
    "                        window[x] -= 1\n",
    "                l += 1\n",
    "                \n",
    "            r += 1\n",
    "        return [lbest, rbest]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        indices = collections.defaultdict(list)\n",
    "        xMin,xMax = 10**9, -10**9\n",
    "        for i, vec in enumerate(nums):\n",
    "            for x in vec:\n",
    "                indices[x].append(i)\n",
    "            xMin = min(xMin,*vec)\n",
    "            xMax = max(xMax,*vec)\n",
    "        freq = [0] * n\n",
    "        inside = 0\n",
    "        left,right = xMin,xMin - 1\n",
    "        bestLeft, bestRight = xMin, xMax\n",
    "\n",
    "        while right < xMax:\n",
    "            right += 1\n",
    "            if right in indices:\n",
    "                for x in indices[right]:\n",
    "                    freq[x] += 1\n",
    "                    if freq[x] == 1:\n",
    "                        inside += 1\n",
    "                while inside == n:\n",
    "                    if right - left < bestRight - bestLeft:\n",
    "                        bestLeft,bestRight = left, right\n",
    "                    if left in indices:\n",
    "                        for x in indices[left]:\n",
    "                            freq[x] -= 1\n",
    "                            if freq[x] == 0:\n",
    "                                inside -= 1\n",
    "                    left += 1\n",
    "        return [bestLeft,bestRight]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        arr = [[num, i] for i, row in enumerate(nums) for num in row]\n",
    "        arr.sort()\n",
    "        # print(arr)\n",
    "\n",
    "        cnts = [0] * len(nums)\n",
    "        valid = 0\n",
    "\n",
    "        a, b = -float('inf'), float('inf')\n",
    "        left, right = 0, 0\n",
    "        while right < len(arr):\n",
    "            # print(left, right)\n",
    "            cnts[arr[right][1]] += 1\n",
    "            if cnts[arr[right][1]] == 1:\n",
    "                valid += 1\n",
    "\n",
    "            while valid == len(nums):\n",
    "                if arr[right][0] - arr[left][0] < b-a:\n",
    "                    a, b = arr[left][0], arr[right][0]\n",
    "\n",
    "                cnts[arr[left][1]] -= 1\n",
    "                if cnts[arr[left][1]] == 0:\n",
    "                    valid -= 1\n",
    "                left += 1\n",
    "\n",
    "            right += 1\n",
    "\n",
    "        return [a, b]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, num, ai, o):\n",
    "        self.num = num\n",
    "        self.arr_index = ai\n",
    "        self.own_index = o\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.num < other.num\n",
    "\n",
    "    def __le__(self, other):\n",
    "        return self.__hash__() < other.__hash__()\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        sorted_set = SortedSet()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            sorted_set.add(Node(nums[i][0], i, 0))\n",
    "        tt = [t.num for t in sorted_set]\n",
    "        left = sorted_set[0].num\n",
    "        right = sorted_set[-1].num\n",
    "        while len(sorted_set) == n:\n",
    "            cur_left = sorted_set[0].num\n",
    "            cur_right = sorted_set[-1].num\n",
    "            if cur_right - cur_left < right - left:\n",
    "                left = cur_left\n",
    "                right = cur_right\n",
    "            pop = sorted_set.pop(0)\n",
    "            p_index = pop.arr_index\n",
    "            p_index_own = pop.own_index\n",
    "            p_arr = nums[p_index]\n",
    "            if p_index_own + 1 < len(p_arr):\n",
    "                sorted_set.add(Node(p_arr[p_index_own + 1], p_index, p_index_own + 1))\n",
    "        return [left, right]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        newNums = []\n",
    "        for i, ns in enumerate(nums):\n",
    "            for x in ns:\n",
    "                newNums.append([x, i])\n",
    "        newNums.sort()\n",
    "        kdict = defaultdict(int)\n",
    "        \n",
    "        l = 0\n",
    "        ans = [inf, inf, inf]\n",
    "        for r, x in enumerate(newNums):\n",
    "            num, kIdx = x\n",
    "            kdict[kIdx] += 1\n",
    "            while len(kdict) == k and kdict[newNums[l][1]] > 1:\n",
    "                kdict[newNums[l][1]] -= 1\n",
    "                l += 1\n",
    "            if len(kdict) == k:\n",
    "                tmp = [newNums[l][0], newNums[r][0], newNums[r][0] - newNums[l][0]]\n",
    "                if tmp[-1] < ans[-1] or (tmp[-1] == ans[-1] and tmp[0] < ans[0]):\n",
    "                    ans = tmp\n",
    "        return ans[:2]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkFeasibility(self, all_list, dict_list_num):\n",
    "        for x in all_list:\n",
    "            if x not in dict_list_num or dict_list_num[x] <= 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def plusR(self, dict_list_num, hashmap_r):\n",
    "        for x in hashmap_r:\n",
    "            if x not in dict_list_num:\n",
    "                dict_list_num[x] = 1\n",
    "            else:\n",
    "                dict_list_num[x] += 1\n",
    "    \n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        checkFeasibility = self.checkFeasibility\n",
    "        plusR = self.plusR\n",
    "        hashmap = dict()\n",
    "        for i in range(len(nums)):\n",
    "            for n in nums[i]:\n",
    "                if n not in hashmap:\n",
    "                    hashmap[n] = {i}\n",
    "                else:\n",
    "                    hashmap[n].add(i)\n",
    "        all_nums = sorted(list(hashmap.keys()))\n",
    "        all_list = set(range(len(nums)))\n",
    "        l, r = 0, 0\n",
    "        dict_list_num = {x: 1 for x in hashmap[all_nums[0]]}\n",
    "        min_cover = [all_nums[0], all_nums[-1]]\n",
    "        while r < len(all_nums):\n",
    "            while not checkFeasibility(all_list, dict_list_num):\n",
    "                r += 1\n",
    "                plusR(dict_list_num, hashmap[all_nums[r]])\n",
    "            while checkFeasibility(all_list, dict_list_num):\n",
    "                l += 1\n",
    "                for x in hashmap[all_nums[l-1]]:\n",
    "                    dict_list_num[x] -= 1\n",
    "            l -= 1\n",
    "            for x in hashmap[all_nums[l]]:\n",
    "                dict_list_num[x] += 1\n",
    "            if (all_nums[r] - all_nums[l]) < min_cover[1] - min_cover[0]:\n",
    "                min_cover = [all_nums[l], all_nums[r]]\n",
    "            r += 1\n",
    "            if r >= len(all_nums):\n",
    "                break\n",
    "            plusR(dict_list_num, hashmap[all_nums[r]])\n",
    "        return min_cover\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        final_list = []\n",
    "        for index_i, info in enumerate(nums):\n",
    "            for _, curnum in enumerate(info):\n",
    "                final_list.append((curnum, index_i))\n",
    "        final_list = sorted(final_list, key = lambda i: i[0])\n",
    "        win_count = [0]* len(nums)\n",
    "        min_len = [final_list[0][0], final_list[-1][0]]\n",
    "        l = 0\n",
    "        for index, num in enumerate(final_list):\n",
    "            r = index\n",
    "            num_index = num[1]\n",
    "            win_count[num_index] += 1\n",
    "            if 0 not in win_count:\n",
    "                #去重\n",
    "                while win_count[final_list[l][1]] >1:\n",
    "                    win_count[final_list[l][1]] -= 1\n",
    "                    l += 1\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            #判断滑窗区间\n",
    "            if (min_len[1]- min_len[0]) > (final_list[r][0] - final_list[l][0]):\n",
    "                min_len = [final_list[l][0], final_list[r][0]]            \n",
    "        return min_len "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        sortNums = sorted((j, inx) for inx, i in enumerate(nums) for j in i)\n",
    "        k = len(sortNums)\n",
    "        L = 0\n",
    "        R = n-1\n",
    "        s, e = sortNums[0][0], sortNums[-1][0]\n",
    "        count = [0]*n\n",
    "        for R in range(k):\n",
    "            count[sortNums[R][1]] += 1\n",
    "            if 0 not in count:\n",
    "                while count[sortNums[L][1]]>1:\n",
    "                    count[sortNums[L][1]] -= 1\n",
    "                    L += 1\n",
    "                mn = sortNums[L][0]\n",
    "                mx = sortNums[R][0]\n",
    "                if mx-mn<e-s:\n",
    "                    s, e = mn, mx\n",
    "        return s, e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        D = collections.defaultdict(set)\n",
    "        nums2 = []\n",
    "        for i, L in enumerate(nums):\n",
    "            for e in L:\n",
    "                D[e].add(i)\n",
    "                nums2.append(e)\n",
    "        nums2 = list(set(nums2)) # 一行代码让运行时间从7012 ms 缩短至80 ms\n",
    "        nums2.sort()\n",
    "        #print(D, nums2)\n",
    "\n",
    "        ans = [nums2[0], nums2[-1]]\n",
    "        counter = [0] * len(nums)\n",
    "        cnt = 0\n",
    "        j = 0\n",
    "        for i in range(len(nums2)):\n",
    "            e = nums2[i]\n",
    "            for idx in D[e]:\n",
    "                if counter[idx] == 0:\n",
    "                    cnt += 1\n",
    "                counter[idx] += 1\n",
    "            while cnt == len(nums):\n",
    "                if nums2[i] - nums2[j] < ans[1] - ans[0]:\n",
    "                    ans = [nums2[j], nums2[i]]\n",
    "                e2 = nums2[j]\n",
    "                for idx in D[e2]:\n",
    "                    counter[idx] -= 1    \n",
    "                    if counter[idx] == 0:\n",
    "                        cnt -= 1\n",
    "                j += 1\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "        a= defaultdict( int )\n",
    "        s=[ ]\n",
    "        for i in range( len( nums )):\n",
    "\n",
    "            for j in nums[i]:\n",
    "                s.append( [ j, i ] ) \n",
    "        s.sort( )\n",
    "        \n",
    "        \n",
    "             \n",
    "\n",
    "        d = defaultdict( list ) \n",
    "        l = 0 \n",
    "        cnt = 0 \n",
    "        n=len( nums ) \n",
    "        for j in range( len(s )): \n",
    "            a[ s[j][1] ] += 1 \n",
    "            if a[ s[j][1]] == 1:\n",
    "                cnt+=1 \n",
    "            if  cnt == n :\n",
    "                while cnt == n  :\n",
    "                    a[ s[l][1] ] -= 1 \n",
    "                   \n",
    "                    if  a[ s[l][1] ] == 0 :\n",
    "                        cnt -= 1 \n",
    "                    l+=1 \n",
    "                d[ s[j][0] - s[l-1][0] + 1  ].append( [s[l-1][0] ,s[j][0] ]) \n",
    "        m=min( d.keys( ) )\n",
    "        print(m, d[m])\n",
    "        return d[m][0] \n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        # sliding window\n",
    "        # low,high\n",
    "        # low==min, high==low\n",
    "        # high++ until satisfy, then low++ while still satisfy,\n",
    "        # update width\n",
    "\n",
    "        # dict to record all num\n",
    "        # record[num]=[list_id,...]#all num, may duplicate in different list\n",
    "        # window[list_id]=set()#elements in current window\n",
    "        # if all(window) then satisfy\n",
    "\n",
    "        record=dict()\n",
    "        for i in range(len(nums)):#i==group id\n",
    "            for num in nums[i]:\n",
    "                if num not in record:\n",
    "                    record[num]={i}\n",
    "                else:#if num in record\n",
    "                    record[num].add(i)\n",
    "        candidates=sorted(list(record.keys()))\n",
    "        #window can only move within candidates            \n",
    "\n",
    "        #elements in current window, window[group_id]\n",
    "        window=[set() for i in range(len(nums))]\n",
    "        low,high=candidates[0],candidates[0]\n",
    "        #low,high can only vary inside candidates, so use candidates[id]\n",
    "        low_id,high_id=0,0\n",
    "        # initial first window, element is {low}\n",
    "        for group_id in record[low]:\n",
    "            window[group_id].add(low)\n",
    "\n",
    "        min_width=float('inf')\n",
    "        min_range=[float('-inf'),float('inf')]\n",
    "        while 1:    \n",
    "            # if not satisfy\n",
    "            if not all(window):\n",
    "                # high++\n",
    "                high_id+=1\n",
    "                if high_id>=len(candidates):break#if reach end\n",
    "                high=candidates[high_id]\n",
    "                # update window, add element {high} to groups\n",
    "                for group_id in record[high]:\n",
    "                    window[group_id].add(high)\n",
    "            #elif satisfy\n",
    "            # if satisfy, update global window width\n",
    "            elif all(window):\n",
    "                current_width=high-low\n",
    "                if current_width<min_width:\n",
    "                    min_width=current_width\n",
    "                    min_range=[low,high]\n",
    "                #low++\n",
    "                # first remove old element {low} from groups\n",
    "                for group_id in record[low]:\n",
    "                    window[group_id].remove(low)\n",
    "                # then update window, \n",
    "                low_id+=1\n",
    "                if low_id>=len(candidates):break#if reach end\n",
    "                low=candidates[low_id]\n",
    "                    \n",
    "        return(min_range)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        retl=min([_[0] for _ in nums])\n",
    "        retr=max([_[0] for _ in nums])\n",
    "        table=[_[0] for _ in nums]\n",
    "        idxs=sorted([[i, j] for i in range(len(nums)) for j in range(1, len(nums[i]))], key=lambda x: nums[x[0]][x[1]])\n",
    "        tl, tr=retl, retr\n",
    "        while len(idxs)>0:\n",
    "            n, idx=idxs.pop(0)\n",
    "            if table[n]==tl:\n",
    "                table[n]=nums[n][idx]\n",
    "                tl=min(table)\n",
    "            else:\n",
    "                table[n]=nums[n][idx]\n",
    "            tr=max(tr, table[n])\n",
    "            if tr-tl<retr-retl:\n",
    "                retl, retr=tl, tr\n",
    "        return [retl, retr]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        ns = sorted(chain(*[[(j, i) for j in nums[i]] for i in range(k)]))\n",
    "        i = 0\n",
    "        j = 0\n",
    "        d = [0] * k\n",
    "        res = [ns[0][0], ns[-1][0]]\n",
    "        while j < len(ns):\n",
    "            d[ns[j][1]] += 1\n",
    "            while d[ns[i][1]] > 1:\n",
    "                d[ns[i][1]] -= 1\n",
    "                i += 1\n",
    "            if 0 not in d:\n",
    "                if ns[j][0] - ns[i][0] < res[-1] - res[0]:\n",
    "                    res = [ns[i][0], ns[j][0]]\n",
    "                elif ns[j][0] - ns[i][0] < res[-1] - res[0] and ns[i][0] < res[0]:\n",
    "                    res = [ns[i][0], ns[j][0]]\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        ns = sorted(chain(*[[(j, i) for j in nums[i]] for i in range(k)]))\n",
    "        i = 0\n",
    "        j = 0\n",
    "        d = [0] * k\n",
    "        res = [ns[0][0], ns[-1][0]]\n",
    "        while j < len(ns):\n",
    "            d[ns[j][1]] += 1\n",
    "            while d[ns[i][1]] > 1:\n",
    "                d[ns[i][1]] -= 1\n",
    "                i += 1\n",
    "            if 0 not in d:\n",
    "                if ns[j][0] - ns[i][0] < res[-1] - res[0]:\n",
    "                    res = [ns[i][0], ns[j][0]]\n",
    "                elif ns[j][0] - ns[i][0] < res[-1] - res[0] and ns[i][0] < res[0]:\n",
    "                    res = [ns[i][0], ns[j][0]]\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j],i))\n",
    "        \n",
    "        lst.sort(key=lambda x:x[0])\n",
    "        i = 0\n",
    "        k = 0\n",
    "        ans = [-10**9, 10**9]\n",
    "        count = {}\n",
    "        for j in range(len(lst)):\n",
    "            if lst[j][1] not in count.keys():\n",
    "                k+=1\n",
    "                count[lst[j][1]] = 1\n",
    "            else:\n",
    "                count[lst[j][1]] += 1\n",
    "            if k==len(nums):\n",
    "                while count[lst[i][1]]>1:\n",
    "                    count[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "                if ans[1]-ans[0]>lst[j][0]-lst[i][0]:\n",
    "                    ans[1],ans[0] = lst[j][0],lst[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j],i))\n",
    "        \n",
    "        lst.sort(key=lambda x:x[0])\n",
    "        i = 0\n",
    "        k = 0\n",
    "        ans = [-10**9, 10**9]\n",
    "        count = {}\n",
    "        for j in range(len(lst)):\n",
    "            if lst[j][1] not in count.keys():\n",
    "                k+=1\n",
    "                count[lst[j][1]] = 1\n",
    "            else:\n",
    "                count[lst[j][1]] += 1\n",
    "            if k==len(nums):\n",
    "                while count[lst[i][1]]>1:\n",
    "                    count[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "                if ans[1]-ans[0]>lst[j][0]-lst[i][0]:\n",
    "                    ans[1],ans[0] = lst[j][0],lst[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        u = []\n",
    "\n",
    "        for i, _ in enumerate(nums):\n",
    "            lv = None\n",
    "\n",
    "            for v in _:\n",
    "                if v != lv:\n",
    "                    u.append((lv := v, i))\n",
    "\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        k = 0\n",
    "        ku = [0] * n\n",
    "        r = [-(10 ** 6), 10 ** 6]\n",
    "\n",
    "        u.sort()\n",
    "\n",
    "        for v, vi in u:\n",
    "            if ku[vi] == 0:\n",
    "                k += 1\n",
    "\n",
    "            ku[vi] += 1\n",
    "\n",
    "            while k == n:\n",
    "                if v - u[i][0] < r[1] - r[0]:\n",
    "                    r = [u[i][0], v]\n",
    "\n",
    "                if ku[u[i][1]] == 1:\n",
    "                    k -= 1\n",
    "\n",
    "                ku[u[i][1]] -= 1\n",
    "                i += 1\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        def check():\n",
    "            for v in cnt:\n",
    "                if not v:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        q = []\n",
    "        for i, row in enumerate(nums):\n",
    "            for v in row:\n",
    "                q.append((v, i))\n",
    "        q.sort()\n",
    "        cnt = [0] * len(nums)\n",
    "        l = r = 0\n",
    "        ans = [q[0][0], q[-1][0]]\n",
    "        while r < len(q):\n",
    "            cnt[q[r][1]] += 1\n",
    "            while check():\n",
    "                if ans[1] - ans[0] > q[r][0] - q[l][0]:\n",
    "                    ans = [q[l][0], q[r][0]]\n",
    "                cnt[q[l][1]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst=[]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j],i))\n",
    "        \n",
    "        lst.sort(key=lambda x: x[0])\n",
    "        i=0\n",
    "        k=0\n",
    "        ans=[-10**9,10**9]\n",
    "        count={}\n",
    "        for j in range(len(lst)):\n",
    "            if lst[j][1] not in count.keys():\n",
    "                k+=1\n",
    "                count[lst[j][1]]=1\n",
    "                \n",
    "            else:\n",
    "                count[lst[j][1]]+=1\n",
    "            \n",
    "            if k==len(nums):\n",
    "                while count[lst[i][1]]>1:\n",
    "                    count[lst[i][1]]-=1\n",
    "                    i+=1\n",
    "                \n",
    "                if ans[1]-ans[0]>lst[j][0]-lst[i][0]:\n",
    "                    ans[1],ans[0]=lst[j][0],lst[i][0]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        arr = []\n",
    "        for rowIdx, row in enumerate(nums):\n",
    "            for num in row:\n",
    "                arr.append((num, rowIdx))\n",
    "        arr.sort()\n",
    "        l = r = 0\n",
    "        cnt = collections.defaultdict(lambda:1)\n",
    "        balance = len(nums)\n",
    "        lans, rans = float(\"-inf\"), float(\"inf\")\n",
    "        while r < len(arr):\n",
    "            cnt[arr[r][1]] -= 1\n",
    "            if cnt[arr[r][1]] == 0:\n",
    "                balance -= 1\n",
    "            while balance == 0 and cnt[arr[l][1]] < 0:\n",
    "                cnt[arr[l][1]] += 1\n",
    "                l += 1\n",
    "            if balance == 0:\n",
    "                if arr[r][0] - arr[l][0] < rans - lans:\n",
    "                    lans, rans = arr[l][0], arr[r][0]\n",
    "            r += 1\n",
    "        print(arr)\n",
    "        return [lans, rans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        snums = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                snums.append((nums[i][j],i))\n",
    "        snums.sort()\n",
    "        d_dict = {}\n",
    "        sset = set()\n",
    "        for i in range(len(nums)):\n",
    "            d_dict[i]=0\n",
    "        l,r = 0,-1\n",
    "        res,resl,resr = float('inf'),0,0\n",
    "        print(snums) \n",
    "        while r<len(snums):\n",
    "            while r+1<len(snums) and len(sset)<len(nums):\n",
    "                r+=1\n",
    "                d_dict[snums[r][1]]+=1\n",
    "                if d_dict[snums[r][1]]==1:\n",
    "                    sset.add(snums[r][1])\n",
    "            if r == len(snums)-1 and len(sset)<len(nums):break\n",
    "            while l<=r and d_dict[snums[l][1]]>1:\n",
    "                d_dict[snums[l][1]] -= 1\n",
    "                l+=1\n",
    "            print(snums[l][0],snums[r][0])\n",
    "            tmp = snums[r][0] - snums[l][0]\n",
    "            if tmp<res:\n",
    "                res,resl,resr = tmp,snums[l][0],snums[r][0]\n",
    "            d_dict[snums[l][1]] -= 1\n",
    "            sset.remove(snums[l][1])\n",
    "            l+=1\n",
    "            if l>r:break\n",
    "        return [resl,resr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        tuple_list=[]\n",
    "        for i in range(len(nums)):\n",
    "            for j in nums[i]:\n",
    "                tuple_list.append((j,i))\n",
    "        sorted_tuple_list=sorted(tuple_list,key=lambda x:x[0])\n",
    "        slow=0\n",
    "        fast=0\n",
    "        class_dict={}\n",
    "        min_len=sorted_tuple_list[-1][0]-sorted_tuple_list[0][0]\n",
    "        interval_start=sorted_tuple_list[0][0]\n",
    "        print(sorted_tuple_list)\n",
    "        while fast<len(sorted_tuple_list):\n",
    "            tup_fast=sorted_tuple_list[fast]\n",
    "            if tup_fast[1] not in class_dict:\n",
    "                class_dict[tup_fast[1]]=1\n",
    "            else:\n",
    "                class_dict[tup_fast[1]]+=1\n",
    "            if len(class_dict)==len(nums):\n",
    "                while class_dict[sorted_tuple_list[slow][1]]>1:\n",
    "                    class_dict[sorted_tuple_list[slow][1]]-=1\n",
    "                    slow+=1\n",
    "                interval=tup_fast[0]-sorted_tuple_list[slow][0]\n",
    "                if interval<min_len:\n",
    "                    min_len=interval\n",
    "                    interval_start=sorted_tuple_list[slow][0]\n",
    "                #print(class_dict,sorted_tuple_list[slow][0],tup_fast[0])\n",
    "                class_dict[sorted_tuple_list[slow][1]]-=1\n",
    "                if class_dict[sorted_tuple_list[slow][1]]==0:\n",
    "                    del class_dict[sorted_tuple_list[slow][1]]\n",
    "                slow+=1\n",
    "                #print(\"rightward:\",class_dict)\n",
    "            fast+=1\n",
    "        return [interval_start,interval_start+min_len]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        ordered = sorted((j,i) for i,a in enumerate(nums) for j in a)\n",
    "        res=[ordered[0][0],ordered[-1][0]]\n",
    "        count = [0]*len(nums)\n",
    "        l=0\n",
    "        for r in range(len(ordered)):\n",
    "            count[ordered[r][1]]+=1\n",
    "            if 0 not in count:\n",
    "                while count[ordered[l][1]]>1:\n",
    "                    count[ordered[l][1]]-=1\n",
    "                    l+=1\n",
    "                if res[1]-res[0]>ordered[r][0]-ordered[l][0]:\n",
    "                    res=[ordered[l][0],ordered[r][0]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        arr = []\n",
    "        table = [0] * k\n",
    "        cnt = 0\n",
    "\n",
    "        for i, row in enumerate(nums):\n",
    "            for x in row:\n",
    "                arr.append([x, i])\n",
    "        arr.sort()\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        i, x, y = 0, inf, inf\n",
    "\n",
    "        for j in range(n):\n",
    "            table[arr[j][1]] += 1\n",
    "            if table[arr[j][1]] == 1:\n",
    "                cnt += 1\n",
    "            while i <= j and cnt == k:\n",
    "                if x == inf or y - x > arr[j][0] - arr[i][0]:\n",
    "                    x, y = arr[i][0], arr[j][0]\n",
    "                table[arr[i][1]] -= 1\n",
    "                if table[arr[i][1]] == 0:\n",
    "                    cnt -= 1\n",
    "                i += 1\n",
    "        return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        arr = []\n",
    "        k = len(nums)\n",
    "        table = [0] * k\n",
    "        cnt = 0\n",
    "\n",
    "        for i, row in enumerate(nums):\n",
    "            for x in row:\n",
    "                arr.append([x, i])\n",
    "        arr.sort()\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        x, y = -inf, -inf\n",
    "        i = 0\n",
    "        \n",
    "        for j in range(n):\n",
    "            table[arr[j][1]] += 1\n",
    "            if table[arr[j][1]] == 1:\n",
    "                cnt += 1\n",
    "            while cnt == k:\n",
    "                if x == -inf or y - x + 1 > arr[j][0] - arr[i][0] + 1:\n",
    "                    x, y = arr[i][0], arr[j][0]\n",
    "                table[arr[i][1]] -= 1\n",
    "                if table[arr[i][1]] == 0:\n",
    "                    cnt -= 1\n",
    "                i += 1\n",
    "        return [x, y]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = list()\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in num:\n",
    "                lst.append((j, i))\n",
    "        lst.sort()\n",
    "        \n",
    "        i = 0\n",
    "        k = 0\n",
    "        ans = [lst[0][0], lst[-1][0]]\n",
    "        count = {}\n",
    "        for j in range(len(lst)):\n",
    "            if lst[j][1] not in count.keys():\n",
    "                k+=1\n",
    "                count[lst[j][1]] = 1\n",
    "            else:\n",
    "                count[lst[j][1]] += 1\n",
    "            if k==len(nums):\n",
    "                while count[lst[i][1]]>1:\n",
    "                    count[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "                if ans[1]-ans[0]>lst[j][0]-lst[i][0]:\n",
    "                    ans[1],ans[0] = lst[j][0],lst[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        arr = []\n",
    "        for i, lst in enumerate(nums):\n",
    "            for x in lst:\n",
    "                arr.append((x, i))\n",
    "        arr.sort()\n",
    "        # cnt[k]: 当前窗口内第 k 个列表有几个元素\n",
    "        cnt = Counter()\n",
    "        ans = None\n",
    "        left = right = 0\n",
    "        group_count = 0\n",
    "        while right < len(arr):\n",
    "            x, group = arr[right][0], arr[right][1]\n",
    "            cnt[group] += 1\n",
    "            if cnt[group] == 1:\n",
    "                group_count += 1\n",
    "            while left < right and cnt[arr[left][1]] > 1:\n",
    "                cnt[arr[left][1]] -= 1\n",
    "                if cnt[arr[left][1]] == 0:\n",
    "                    group_count -= 1\n",
    "                left += 1\n",
    "            if group_count == len(nums):\n",
    "                if ans is None or arr[right][0] - arr[left][0] < ans[1] - ans[0]:\n",
    "                    ans = [arr[left][0], arr[right][0]]\n",
    "            right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        A = sorted((a,x) for x,arr in enumerate(nums) for a in arr)\n",
    "        res, i = [-inf,inf], 0\n",
    "        ct = defaultdict(int)\n",
    "        for a,x in A:\n",
    "            ct[x]+=1\n",
    "            while len(ct)==k:\n",
    "                b, y = A[i]\n",
    "                if a-b<res[1]-res[0]:\n",
    "                    res = [b,a]\n",
    "                ct[y] -= 1\n",
    "                if not ct[y]:\n",
    "                    del ct[y]\n",
    "                i += 1\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        seen = collections.defaultdict(set)\n",
    "        for i, num in enumerate(nums):\n",
    "            for n_ in num:\n",
    "                seen[n_].add(i)\n",
    "        skeys = sorted(seen)\n",
    "        cntk = [0] * k\n",
    "        res = [skeys[0], skeys[-1]]\n",
    "        lack, left = k, 0\n",
    "        for right, key in enumerate(skeys):\n",
    "            for idx in seen[key]:\n",
    "                cntk[idx] += 1\n",
    "                if cntk[idx] == 1:\n",
    "                    lack -= 1\n",
    "            while lack == 0:\n",
    "                if key - skeys[left] < res[1] - res[0]:\n",
    "                    res = [skeys[left], key]\n",
    "                for idx in seen[skeys[left]]:\n",
    "                    cntk[idx] -= 1\n",
    "                    if cntk[idx] == 0:\n",
    "                        lack += 1\n",
    "                left += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        d = collections.defaultdict(set)\n",
    "        for i, num in enumerate(nums):\n",
    "            for n_ in num:\n",
    "                d[n_].add(i)\n",
    "\n",
    "        sortedKeys = sorted(d)\n",
    "        n = len(sortedKeys)\n",
    "        cntk = [0] * k\n",
    "        res = [sortedKeys[0], sortedKeys[-1]]\n",
    "        cnt = right = 0\n",
    "        for left, key in enumerate(sortedKeys):\n",
    "            while right < n and cnt < k:\n",
    "                for idx in d[sortedKeys[right]]:\n",
    "                    cntk[idx] += 1\n",
    "                    if cntk[idx] == 1:\n",
    "                        cnt += 1\n",
    "                right += 1\n",
    "            if cnt == k:\n",
    "                if sortedKeys[right - 1] - key < res[1] - res[0]:\n",
    "                    res = [key, sortedKeys[right - 1]]\n",
    "            for idx in d[sortedKeys[left]]:\n",
    "                cntk[idx] -= 1\n",
    "                if cntk[idx] == 0:\n",
    "                    cnt -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j], i))\n",
    "\n",
    "        res = [-(10 ** 5), 10 ** 5]\n",
    "        lst.sort(key=lambda x: x[0])\n",
    "        counter = collections.Counter()\n",
    "        i, k = 0, 0\n",
    "        for j in range(len(lst)):\n",
    "            if counter[lst[j][1]] == 0:\n",
    "                k += 1\n",
    "            counter[lst[j][1]] += 1\n",
    "            if k == n:\n",
    "                while counter[lst[i][1]] > 1:\n",
    "                    counter[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "\n",
    "                if res[1] - res[0] > lst[j][0] - lst[i][0]:\n",
    "                    res[1], res[0] = lst[j][0], lst[i][0]\n",
    "        return res\n",
    "\n",
    "\n",
    "# 起始时，窗口左侧指向0号位置，窗口右侧一直向右滑动，直到窗口内包含k组数。\n",
    "# 此时窗口左侧开始收缩，直到窗口左侧元素是该组唯一的元素。\n",
    "# 此时窗口左侧到窗口右侧就是最小区间。\n",
    "# 此后窗口右侧继续向右滑动，每滑动一次，就判断窗口左侧是否需要收缩，即判断窗口左侧元素是否是该组唯一的元素，如果是，收缩窗口左侧，直到窗口左侧元素是该组唯一的元素。\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "#         lst = []\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             for j in range(len(nums[i])):\n",
    "#                 lst.append((nums[i][j], i))\n",
    "#         res = [-(10 ** 5), 10 ** 5]\n",
    "#         lst.sort(key=lambda x: x[0])\n",
    "#         i, k = 0, 0\n",
    "#         count = collections.Counter()\n",
    "#         for j in range(len(lst)):\n",
    "#             if count[lst[j][1]] == 0:\n",
    "#                 k += 1\n",
    "#             count[lst[j][1]] += 1\n",
    "#             if k == n:\n",
    "#                 while count[lst[i][1]] > 1:\n",
    "#                     count[lst[i][1]] -= 1\n",
    "#                     i += 1\n",
    "#                 if res[1] - res[0] > lst[j][0] - lst[i][0]:\n",
    "#                     res[1], res[0] = lst[j][0], lst[i][0]\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(len(nums[i])):\n",
    "                lst.append((nums[i][j], i))\n",
    "        res = [-(10 ** 5), 10 ** 5]\n",
    "        lst.sort(key=lambda x: x[0])\n",
    "        i, k = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        for j in range(len(lst)):\n",
    "            if counter[lst[j][1]] == 0:\n",
    "                k += 1\n",
    "            counter[lst[j][1]] += 1\n",
    "            if k == n:\n",
    "                while counter[lst[i][1]] > 1:\n",
    "                    counter[lst[i][1]] -= 1\n",
    "                    i += 1\n",
    "\n",
    "                if res[1] - res[0] > lst[j][0] - lst[i][0]:\n",
    "                    res[1], res[0] = lst[j][0], lst[i][0]\n",
    "        return res\n",
    "\n",
    "\n",
    "# 起始时，窗口左侧指向0号位置，窗口右侧一直向右滑动，直到窗口内包含k组数。\n",
    "# 此时窗口左侧开始收缩，直到窗口左侧元素是该组唯一的元素。\n",
    "# 此时窗口左侧到窗口右侧就是最小区间。\n",
    "# 此后窗口右侧继续向右滑动，每滑动一次，就判断窗口左侧是否需要收缩，即判断窗口左侧元素是否是该组唯一的元素，如果是，收缩窗口左侧，直到窗口左侧元素是该组唯一的元素。\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "#         lst = []\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             for j in range(len(nums[i])):\n",
    "#                 lst.append((nums[i][j], i))\n",
    "#         res = [-(10 ** 5), 10 ** 5]\n",
    "#         lst.sort(key=lambda x: x[0])\n",
    "#         i, k = 0, 0\n",
    "#         count = collections.Counter()\n",
    "#         for j in range(len(lst)):\n",
    "#             if count[lst[j][1]] == 0:\n",
    "#                 k += 1\n",
    "#             count[lst[j][1]] += 1\n",
    "#             if k == n:\n",
    "#                 while count[lst[i][1]] > 1:\n",
    "#                     count[lst[i][1]] -= 1\n",
    "#                     i += 1\n",
    "#                 if res[1] - res[0] > lst[j][0] - lst[i][0]:\n",
    "#                     res[1], res[0] = lst[j][0], lst[i][0]\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        he = []\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            m = len(num)\n",
    "\n",
    "            for j in range(m):\n",
    "                he.append((num[j], i))\n",
    "        \n",
    "\n",
    "        he.sort(key = lambda x : x[0])\n",
    "\n",
    "        # print(he)\n",
    "        res = []\n",
    "        dt = [0] * n\n",
    "        o = len(he)\n",
    "        i, j, k = 0, 0, 0\n",
    "        while j < o:\n",
    "            if dt[he[j][1]] == 0:\n",
    "                k += 1\n",
    "            dt[he[j][1]] += 1\n",
    "            if k == n:\n",
    "                \n",
    "                while dt[he[i][1]] > 1:\n",
    "                    dt[he[i][1]] -= 1\n",
    "                    i += 1\n",
    "                # print(j, i)\n",
    "                if not res or res[1] - res[0] > he[j][0] - he[i][0]:\n",
    "                    res = [he[i][0], he[j][0]]\n",
    "            j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "        arr=[]\n",
    "\n",
    "        for i,v in enumerate(nums):\n",
    "            for x in v:\n",
    "                arr.append([x,i])\n",
    "        cnt=collections.Counter()\n",
    "        n=len(nums)\n",
    "        arr.sort()\n",
    "        #print(arr)\n",
    "        l=0\n",
    "        ans=[]\n",
    "        mx=float(\"inf\")\n",
    "        for j in range(len(arr)):\n",
    "            ind=arr[j][1]\n",
    "            cnt[ind]+=1\n",
    "            while len(cnt.keys())==n:\n",
    "                tmp=arr[j][0]-arr[l][0]\n",
    "                #print(arr[j][0],arr[l][0],tmp)\n",
    "                if mx>tmp:\n",
    "                    mx=tmp\n",
    "                    ans=[arr[l][0],arr[j][0]]\n",
    "                ind1=arr[l][1]\n",
    "                cnt[ind1]-=1\n",
    "                if cnt[ind1]==0:\n",
    "                    del(cnt[ind1])\n",
    "                l=l+1\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\r\n",
    "        # slide window on array of sorted numbers, count row appearances in window\r\n",
    "        arr = sorted((num, i) for i, row in enumerate(nums) for num in row)\r\n",
    "        win: dict[int, int] = dict()\r\n",
    "        res: list[int] = list()\r\n",
    "        j = 0\r\n",
    "        m = len(nums)\r\n",
    "        for num, i in arr:\r\n",
    "            win.setdefault(i, 0)\r\n",
    "            win[i] += 1\r\n",
    "            while len(win) == m:\r\n",
    "                if not res or res[1] - res[0] > num - arr[j][0]:\r\n",
    "                    res = [arr[j][0], num]\r\n",
    "                win[arr[j][1]] -= 1\r\n",
    "                if win[arr[j][1]] == 0:\r\n",
    "                    del win[arr[j][1]]\r\n",
    "                j += 1\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for k, v in enumerate(nums):\n",
    "            m1[k] = deque(v)\n",
    "        sd1 = SortedList(key=lambda x: x[1])\n",
    "        for i in m1:\n",
    "            first = m1[i].popleft()\n",
    "            sd1.add((i, first))\n",
    "        ans = math.inf\n",
    "        ret = []\n",
    "        while True:\n",
    "            ans1 = sd1[-1][1] - sd1[0][1]\n",
    "            if ans1 < ans:\n",
    "                ans = ans1\n",
    "                ret = [sd1[0][1], sd1[-1][1]]\n",
    "            idx, _ = sd1.pop(0)\n",
    "            if len(m1[idx]) == 0:\n",
    "                break\n",
    "            sd1.add((idx, m1[idx].popleft()))\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        tmp = []\n",
    "        for i, num in enumerate(nums):\n",
    "            for v in num:\n",
    "                tmp.append([v, i])\n",
    "        tmp.sort(key=lambda x: x[0])\n",
    "\n",
    "        res = []\n",
    "        k = len(nums)\n",
    "        count = defaultdict(int) \n",
    "        left = 0\n",
    "\n",
    "        for right, v in enumerate(tmp):\n",
    "            count[v[1]] += 1\n",
    "            while len(count) == k:\n",
    "                if not res or tmp[right][0] - tmp[left][0] < res[1] - res[0]:\n",
    "                    res = [tmp[left][0], tmp[right][0]]\n",
    "\n",
    "                count[tmp[left][1]] -= 1\n",
    "                if count[tmp[left][1]] == 0:\n",
    "                    del count[tmp[left][1]]\n",
    "                \n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "        arr=[]\n",
    "\n",
    "        for i,v in enumerate(nums):\n",
    "            for x in v:\n",
    "                arr.append([x,i])\n",
    "        cnt=collections.Counter()\n",
    "        n=len(nums)\n",
    "        arr.sort()\n",
    "        #print(arr)\n",
    "        l=0\n",
    "        ans=[]\n",
    "        mx=float(\"inf\")\n",
    "        for j in range(len(arr)):\n",
    "            ind=arr[j][1]\n",
    "            cnt[ind]+=1\n",
    "            while len(cnt.keys())==n:\n",
    "                tmp=arr[j][0]-arr[l][0]\n",
    "                print(arr[j][0],arr[l][0],tmp)\n",
    "                if mx>tmp:\n",
    "                    mx=tmp\n",
    "                    ans=[arr[l][0],arr[j][0]]\n",
    "                ind1=arr[l][1]\n",
    "                cnt[ind1]-=1\n",
    "                if cnt[ind1]==0:\n",
    "                    del(cnt[ind1])\n",
    "                l=l+1\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        d = Counter()\n",
    "        arr = []\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, x in enumerate(num):\n",
    "                arr.append((x, i))\n",
    "        arr.sort()\n",
    "        \n",
    "        l, res = 0, [-inf, inf]\n",
    "        for r, (num, i) in enumerate(arr):\n",
    "            d[i] += 1\n",
    "            while len(d) == n:\n",
    "                if arr[r][0] - arr[l][0] < res[1] - res[0]:\n",
    "                    res[0], res[1] = arr[l][0], arr[r][0]\n",
    "                d[arr[l][1]] -= 1\n",
    "                if d[arr[l][1]] == 0:\n",
    "                    d.pop(arr[l][1])\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, lists: List[List[int]]) -> List[int]:\n",
    "        arr = sorted(sum(([(x, i) for x in nums] for i, nums in enumerate(lists)), []))\n",
    "        cnt = defaultdict(int)\n",
    "        l = 0\n",
    "        left, right = arr[0][0], arr[-1][0]\n",
    "        for r, (x, i) in enumerate(arr):\n",
    "            cnt[i] += 1\n",
    "            if len(cnt) < len(lists):\n",
    "                continue\n",
    "            while l < r and cnt[arr[l][1]] > 1:\n",
    "                cnt[arr[l][1]] -= 1\n",
    "                l += 1\n",
    "            if x - arr[l][0] < right - left:\n",
    "                left, right = arr[l][0], x\n",
    "        return [left, right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        i = 0\n",
    "        nums1 =[]\n",
    "        while i < len(nums):\n",
    "            temp = []\n",
    "            for value in nums[i]:\n",
    "                if value not in temp:\n",
    "                    temp.append(value)\n",
    "                    nums1.append([value,i])\n",
    "            i += 1\n",
    "        #nums1 = list(set(nums1))\n",
    "        sort_d = [value for index, value in sorted(enumerate(nums1), key=lambda nums1:nums1[1])]\n",
    "        #print(sort_d)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        list1 = []\n",
    "        list0 = []\n",
    "        temp = []\n",
    "        min1 = 2*pow(10,5)\n",
    "        minlist = []\n",
    "        while i < len(sort_d):\n",
    "            list0.append(sort_d[i][0])\n",
    "            list1.append(sort_d[i][1])\n",
    "            if sort_d[i][1] not in temp:\n",
    "                temp.append(sort_d[i][1])\n",
    "            while len(temp) == len(nums):#去掉重复元素 查看是否每个list都涵盖\n",
    "                if list0[-1] - list0[0] < min1:#左边开始缩小\n",
    "                    min1 = list0[-1] - list0[0]\n",
    "                    minlist = [list0[0],list0[(-1)]]\n",
    "                list0.remove(sort_d[j][0])\n",
    "                list1.remove(sort_d[j][1])\n",
    "                if sort_d[j][1] not in list1:\n",
    "                    temp.remove(sort_d[j][1])\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return minlist\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        numsSet = []\n",
    "        for i, num in enumerate(nums):\n",
    "            for x in num:\n",
    "                numsSet.append((x, i))\n",
    "        numsSet.sort(key=lambda a: a[0])\n",
    "        left = 0\n",
    "        ans = [-10**9, 10**9]\n",
    "        cnt = [0]*m\n",
    "        for i in range(len(numsSet)):\n",
    "            rightVal = numsSet[i][0]\n",
    "            rightGroup = numsSet[i][1]\n",
    "            if cnt[rightGroup] == 0:\n",
    "                m -= 1\n",
    "            cnt[rightGroup] += 1\n",
    "            if m == 0:\n",
    "                while cnt[numsSet[left][1]] > 1:\n",
    "                    cnt[numsSet[left][1]] -= 1\n",
    "                    left += 1\n",
    "                leftVal = numsSet[left][0]\n",
    "                if ans[1]-ans[0] > rightVal-leftVal:\n",
    "                    ans[0] = leftVal\n",
    "                    ans[1] = rightVal\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        num_tmp =[]\n",
    "        min_max=10e5\n",
    "        max_min = -10e5\n",
    "        for idx,nums_i in enumerate(nums):\n",
    "            min_max=min(min_max,nums_i[-1])\n",
    "            max_min = max(max_min,nums_i[0])\n",
    "            for ele in nums_i:\n",
    "                num_tmp.append([ele,idx])\n",
    "        num_tmp=sorted(num_tmp,key=(lambda a:a[0]))\n",
    "\n",
    "        i=0\n",
    "        k=0\n",
    "        count={}\n",
    "        res = [-10e5,10e5]\n",
    "        for j in range(len(num_tmp)):\n",
    "            if num_tmp[j][1] not in count.keys():\n",
    "                count[num_tmp[j][1]]=1\n",
    "                k+=1\n",
    "            else:\n",
    "                count[num_tmp[j][1]] +=1\n",
    "            if(k==len(nums)):\n",
    "                while count[num_tmp[i][1]]>1:\n",
    "                    count[num_tmp[i][1]]-=1\n",
    "                    i += 1\n",
    "                if res[1]-res[0]>num_tmp[j][0]-num_tmp[i][0]:\n",
    "                    res[0]=num_tmp[i][0]\n",
    "                    res[1] = num_tmp[j][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRange(self, nums: List[List[int]]) -> List[int]:\n",
    "        k = len(nums)\n",
    "        rec = []\n",
    "        for i in range(k):\n",
    "            rec.extend([(e,i) for e in nums[i]])\n",
    "        rec.sort(key=lambda x:x[0])\n",
    "        n = len(rec)\n",
    "\n",
    "        freq = [0]*k\n",
    "        exist_num = 0\n",
    "        l,r = 0,0\n",
    "        min_len = float('inf')\n",
    "        res_left, res_right = -1,-1\n",
    "        while r<n:\n",
    "            freq[rec[r][1]]+=1\n",
    "            if freq[rec[r][1]]==1:\n",
    "                exist_num+=1\n",
    "            if exist_num==k:\n",
    "                while freq[rec[l][1]]>1:\n",
    "                    freq[rec[l][1]]-=1\n",
    "                    l+=1\n",
    "                if rec[r][0]-rec[l][0]<min_len:\n",
    "                    min_len = rec[r][0]-rec[l][0]\n",
    "                    res_left,res_right = rec[l][0],rec[r][0]\n",
    "                freq[rec[l][1]]-=1\n",
    "                exist_num -= 1\n",
    "                l+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r+=1\n",
    "        return [res_left, res_right]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
